# 变量命名特点：所有单个单词首字母小写，所有两个单词连写则第一个首字母小写，第二个首字母大写。
class Vertex:
    '''将每个棋盘状况做成节点，包括当前轮到谁的信息等等。'''

    def __init__(self, board, belong, player, currentRound=None, mode=None, parent=None):
        self.board = board  # 棋盘
        self.belong = belong  # 当前棋局（即将）行动方
        self.player = player  # 玩家自己（即Player类）
        self.round = currentRound  # 当前轮数
        self.mode = mode  # 当前模式
        self.parent = parent  # 父节点
        self.child = {}  # 子节点的字典：{做出的行动:子节点}
        self.orderedMove = []  # 根据行动方的对手还是自己，将考虑的行动排序，更有效剪枝。
        self.alpha = float('-inf')  # 下界
        self.beta = float('inf')  # 上界
        self.boardValue = None  # 静态估值函数，先用这个凑合一下，要更改函数只需要改此一处。
        self.searchValue = None  # 搜索后估值
        self.bestchoice = None  # （行动方）最佳策略
        self.winner = None  # 胜利方

    def getWinner(self):  # 判断输赢
        myself = tuple(reversed(self.board.getScore(self.player.belong)))
        myRival = tuple(reversed(self.board.getScore(not self.player.belong)))
        if myself >= myRival:  # 平局算自己赢
            return self.player.belong
        else:
            return not self.player.belong

    def getNone(self):  # 重写这个方法是为了获得一个顺序更合理的位置列表 5.25日
        if self.belong:
            return [(i, j) for j in range(4, 8) for i in range(4) if not self.board.getValue((i, j))]
        else:
            return [(i, j) for j in range(3, -1, -1) for i in range(4) if not self.board.getValue((i, j))]

    def setRange(self, alpha, beta):
        self.alpha = alpha
        self.beta = beta

    def expand(self):
        '''生成当前节点的子节点'''
        if self.mode == 'position':  # 时间上进行了优化，只需要copy一次了
            another = self.board.getNext(self.belong, self.round)
            available = self.getNone()
            if another != ():
                imitation = self.board.copy()
                imitation.add(self.belong, another)  # 棋盘模拟
                vertex = Vertex(imitation, not self.belong, self.player, self.round, parent=self)  # 各种参数设置
                self.child[another] = vertex  # 建立子节点关联
                vertex.mode = 'position' if self.belong else 'direction'  # 模式设置

            if available:
                bestPos = max(available,
                              key=lambda pos: self.player.cost_function_1(self.board, pos, not self.belong))
                imitation = self.board.copy()
                imitation.add(self.belong, bestPos)
                vertex = Vertex(imitation, not self.belong, self.player, self.round, parent=self)
                self.child[bestPos] = vertex
                vertex.mode = 'position' if self.belong else 'direction'

            if self.child == {}:  # 考虑到无棋可走的可能
                if self.belong:  # 此时游戏结束。
                    self.winner = self.getWinner()
                    return  # 省时间
                imitation = self.board.copy()
                vertex = Vertex(imitation, not self.belong, self.player, self.round, parent=self)
                self.child[()] = vertex
                vertex.mode = 'position' if self.belong else 'direction'

        elif self.mode == 'direction':
            directionList = [3, 2, 1, 0] if self.belong else [2, 3, 1, 0]
            for direction in directionList:
                imitation = self.board.copy()
                if imitation.move(self.belong, direction):
                    vertex = Vertex(imitation, not self.belong, self.player, self.round, parent=self)
                    self.child[direction] = vertex
                    vertex.mode = 'direction' if self.belong else 'position'
                    vertex.round += 0 if self.belong else 1  # 如果是后手，子节点回合数将+1
            if self.child == {}:
                imitation = self.board.copy()
                vertex = Vertex(imitation, not self.belong, self.player, self.round, parent=self)
                self.child[()] = vertex
                vertex.mode = 'direction' if self.belong else 'position'
                vertex.round += 0 if self.belong else 1
        else:
            return

    def search(self, depth):
        '''相应深度的alpha-beta搜索，同时返回搜索有效性。所谓有效性，指它能否严格更新父节点的需求值。'''
        if depth >= 1:
            if self.round >= 500:  # 此时游戏结束。
                self.winner = self.getWinner()
            if self.winner == True or self.winner == False:  # 胜负已分，估值直接判定为正/负无穷。
                if self.winner == self.player.belong:
                    self.boardValue = 2 ** 21
                else:
                    self.boardValue = -2 ** 21
                if self.player.belong == self.belong:
                    self.alpha = self.boardValue
                else:
                    self.beta = self.boardValue
                if self.alpha >= self.beta:
                    return False
                else:
                    self.searchValue = self.boardValue
                    return True

            self.expand()  # 生成子节点  (放到后面来，省时间)
            bestchoice = None
            for move in self.child:
                self.child[move].setRange(self.alpha, self.beta)
                if self.child[move].search(depth - 1):  # 递归地深度搜索
                    if self.player.belong == self.belong:
                        self.alpha = self.child[move].searchValue
                    else:
                        self.beta = self.child[move].searchValue
                    bestchoice = move
                if self.alpha >= self.beta:  # 这里是大于等于，意味着相同估值时，先遍历的优先。
                    return False  # 此时搜索无效
                # 如果子节点全部返回False，表示它的真实值一定大于beta或小于alpha,所以它的更新是一定成功的。
                # 投机取巧地，它拿≥beta或≤alpha的真实值并返回True会导致它的父节点返回False。所以它拿β或α效果是一样的。
            self.bestchoice = bestchoice
            if self.player.belong == self.belong:
                self.searchValue = self.alpha
            else:
                self.searchValue = self.beta
            return True

        elif depth == 0:  # 递归的最简情况
            self.boardValue = self.player.cost_function_2(self.board, self.round)
            if self.player.belong == self.belong:
                self.alpha = self.boardValue
            else:
                self.beta = self.boardValue
            if self.alpha >= self.beta:
                return False
            else:
                self.searchValue = self.boardValue
                return True
        else:
            return False


class Player:
    def __init__(self, isFirst: bool, array: list) -> None:
        self.belong = isFirst
        self.array = array
        self.height = 4
        self.width = 8
        self.half_width = 4
        # self.empty_score = 12  # 在代价函数中每个空位对应的得分，12分等价于一个数字为8的格子的得分
        # self.rival_empty_score = 12  # 本次修改新增的属性，鼓励AI将对方的棋子吃掉后将棋子移回本方
        """移除了空位得分 5.24日"""

    def output(self, currentRound, board, mode):
        if mode == "direction" or mode == "position":
            self.searchTree = Vertex(board, self.belong, self, currentRound, mode, parent=None)
            depth = 4 if mode == "direction" else 2  # 设置为正数，否则将返回None
            self.searchTree.search(depth)
            return self.searchTree.bestchoice
        else:
            return

    def cost_function(self, chessboard, mode, currentRound, position=None, belong=True):
        """如果模式是position，调用时就需要给出落子的位置和归属，
        True表示下在先手方，False表示下在后手方，模式是direction
        就不需要给出position和belong参数"""
        if mode == "position":
            return self.cost_function_1(chessboard, position, belong)
        else:
            return self.cost_function_2(chessboard, currentRound)

    def cost_function_1(self, chessboard, position: tuple, belong: bool):  # 对应mode为放棋子的情况,第一个代价函数
        score = 0
        if self.belong == belong:  # 表明棋子下在自己这边
            up = self.get_neighbor_2(chessboard, position, 0)  # 获取该位置上方的棋子值
            down = self.get_neighbor_2(chessboard, position, 1)  # 获取该位置下方的棋子值
            left = self.get_neighbor_2(chessboard, position, 2)  # 获取该位置左方的棋子值
            right = self.get_neighbor_2(chessboard, position, 3)  # 获取该位置右方的棋子值
            score += self.put_chessman_score(up, down, left, right)
            return score
        else:  # 表明棋子下在对方那,此时棋子属于对方
            up = self.get_neighbor_3(chessboard, position, 0)  # 获取该位置上方的棋子值
            down = self.get_neighbor_3(chessboard, position, 1)  # 获取该位置下方的棋子值
            left = self.get_neighbor_3(chessboard, position, 2)  # 获取该位置左方的棋子值
            right = self.get_neighbor_3(chessboard, position, 3)  # 获取该位置右方的棋子值
            score += self.put_chessman_score(up, down, left, right)
            return score

    def cost_function_2(self, chessboard, currentRound):  # 对应的mode是移动的情况
        score = 0
        another_score = 0  # 考虑总分的影响,5.25日修改
        for position in self.return_pos(self.belong):  # 对己方的16个格子进行遍历
            if chessboard.getBelong(position) != self.belong:  # 说明己方位置被对方占了
                score += self.be_occupied_score(chessboard.getValue(position))
                score += self.rival_chessman_score(chessboard.getValue(position))
                another_score -= pow(2, chessboard.getValue(position))
                """相比于其它情况，己方位置被占减少的分数比对应更大，
                这样就可以鼓励AI在能够将该位置的棋子吃掉尽可能选择吃掉"""
            else:  # 对应的该位置是属于自己的
                # if position not in chessboard.board:
                # score += self.empty_score  # 空位也是非常宝贵的！
                if chessboard.getValue(position):  # 此位置有自己的棋子，score加上棋子对应的分值,还有所处棋局形势对应的分值
                    for direction in range(4):
                        score += self.situation_score(chessboard, position, direction, currentRound)
                    score += self.my_chessman_score(chessboard.getValue(position))
                    another_score += pow(2, chessboard.getValue(position))

        for position in self.return_pos(not self.belong):  # 对对方的16个格子进行遍历
            if chessboard.getBelong(position) == self.belong:  # 说明对方位置被己方占了
                score += self.occupy_score(chessboard.getValue(position))
                score += self.my_chessman_score(chessboard.getValue(position))
                another_score += pow(2, chessboard.getValue(position))
                for direction in range(4):
                    score += self.situation_score(chessboard, position, direction, currentRound)
            else:
                if chessboard.getValue(position):
                    score += self.rival_chessman_score(chessboard.getValue(position))
                    another_score -= pow(2, chessboard.getValue(position))
                    # 对应的情况是这个位置属于对方且上面有棋
                # else:
                # score += self.rival_empty_score  # 本次修改新增加的情况,移动后对方的空位越多越好
        return score + another_score * 2

    def situation_score(self, chessboard, position: tuple, direction: int, currentRound) -> int:
        """该函数用于判断己方某棋子目前所处的状态(因此传入的position要求对应己方棋子)，
        主要依据是看它是否存在被对方吃的可能性，或者能安全吃掉对方的可能性，
        但是没有考虑存在陷阱的情况(见下面的讨论),返回值是该状态对应的得分
        用于在mode为direction时调用"""
        is_adjacent = True  # 该参数用于判断position是否安全
        next_position = self.update_position(position, direction)
        if not self.is_in_chess(next_position):  # 表明不能在该方向上继续移动,返回0分
            return 0
        while self.is_in_chess(next_position) and (chessboard.getValue(next_position) == 0) \
                and self.belong == chessboard.getBelong(next_position):
            # 表明该格子为空且属于自己,继续向前走
            is_adjacent = False  # 表明该棋子在该方向上没有直接相邻敌对格，因此不存在被吃风险,是安全的
            next_position = self.update_position(next_position, direction)
        if not self.is_in_chess(next_position):
            return 0  # 此时该棋子不位于边界，且该方向上没有棋子,返回0分
        elif self.belong != chessboard.getBelong(next_position):
            # 说明该格子属于对方
            if chessboard.getValue(next_position):  # 这表明不仅格子属于对方，而且上面还有棋
                if is_adjacent:  # 表明初始位置和最终的next_position相邻
                    if chessboard.getValue(next_position) == chessboard.getValue(position):
                        return self.threaten_score(chessboard.getValue(position))  # 进攻型改为正分
                        # 此时未考虑故意吸引的可能性：比如己方在另一个方向恰好有2倍的值，在对方吃掉这颗棋后可以马上把对方的棋吃掉
                    else:
                        return 0  # 此时相邻的对方棋与自己值不相等，不构成威胁
                else:
                    # 说明此时初始位置与最终的next_position不相邻，因此我方可以吃它，但它不能吃我方
                    if chessboard.getValue(next_position) == chessboard.getValue(position):
                        return 2 * self.threaten_score(chessboard.getValue(position))  # 可以吃对面，局势有利
                        # 此时也未考虑对方故意吸引的可能性：理由同上
                    else:
                        return 0  # 此时对方的棋与己方的棋值不相等，
            else:  # 此时该格子属于对方，但是上面没有棋
                if is_adjacent:  # 表明初始位置有被对方吃的可能性
                    while self.is_in_chess(next_position) and (chessboard.getValue(next_position) == 0):
                        # 继续向指定方向走直到碰到有棋子为止
                        next_position = self.update_position(next_position, direction)
                    if not self.is_in_chess(next_position):
                        return 0  # 表明从初始位置沿该方向上无棋子
                    elif self.belong == chessboard.getBelong(next_position):
                        # 考虑到存在有己方棋子跑到人家人家棋盘的可能性
                        return 0  # 此时初始位置的棋子不存在被吃的可能性
                    else:
                        # 对应的情况是有对方棋子
                        if chessboard.getValue(next_position) == chessboard.getValue(position):
                            return -2 * self.threaten_score(chessboard.getValue(position))  # 此时有被对方吃的可能性,返回负分
                        else:
                            return 0  # 此时无威胁
                else:
                    # 此时对方吃不到自己，没有威胁
                    return 0
        else:
            # 该情况意味着从初始位置出发沿指定方向移动碰到的第一个棋子是自己人
            if chessboard.getValue(next_position) == chessboard.getValue(position) and currentRound >= 70:
                return pow(2, chessboard.getValue(position))
            else:
                return 0

    def get_neighbor_2(self, chessboard, position: tuple, direction: int):
        """该函数在下棋模式调用，且对应下在己方位置的情况，
        用于获取该棋子在该方向上相邻的己方棋子"""
        next_position = self.update_position(position, direction)

        while self.is_in_chess(next_position) and (chessboard.getValue(next_position) == 0) \
                and self.belong == chessboard.getBelong(next_position):
            next_position = self.update_position(next_position, direction)
        if self.is_in_chess(next_position) and self.belong == chessboard.getBelong(next_position):
            return chessboard.getValue(next_position), True  # 得到相邻的己方棋，返回分值和True
        elif self.is_in_chess(next_position) and chessboard.getValue(next_position) >= 2:
            return chessboard.getValue(next_position), False  # 得到相邻的对手棋，返回分值和False
        else:
            return False  # 对应该方向上没有己方棋子

    def get_neighbor_3(self, chessboard, position: tuple, direction: int):
        """该函数在下棋模式调用，且对应下在对方位置的情况
        用于获取该棋子在该方向上相邻的对方棋子(此时该棋子是属于对方的)"""
        next_position = self.update_position(position, direction)
        while self.is_in_chess(next_position) and (chessboard.getValue(next_position) == 0) \
                and self.belong != chessboard.getBelong(next_position):
            next_position = self.update_position(next_position, direction)
        if self.is_in_chess(next_position) and self.belong != chessboard.getBelong(next_position):
            return chessboard.getValue(next_position), False  # 得到相邻的对方棋，返回分值和False
        elif self.is_in_chess(next_position) and chessboard.getValue(next_position) >= 2:
            return chessboard.getValue(next_position), True  # 得到相邻的己方棋，返回分值和True
        else:
            return False  # 对应该方向上没有对方的棋子

    def return_pos(self, belong):
        if belong:  # 返回先手方的遍历格子
            for i in range(self.height):
                for j in range(self.half_width):
                    yield i, j
        else:  # 返回后手方的遍历格子
            for i in range(self.height):
                for j in range(self.half_width, self.width):
                    yield i, j

    def is_in_chess(self, position):  # 用于判断该位置是否在棋盘中
        return (0 <= position[0] < self.height) and (0 <= position[1] < self.width)

    # is_in_chess进行了修改，之前width和height写反了  修改时间,5.18,20:49

    @staticmethod
    def my_chessman_score(value):  # 返回己方每个值对应多少得分,封装在函数中便于修改,在移动模式的代价函数中调用
        return value * int(pow(2, value))
        # 没有直接返回2的value次方是为了鼓励AI尽可能合并大的

    """my_chessman_score进行了修改，原来是3*2**value,意识到
    如果是仅仅把value放在指数上不能实现鼓励AI合并的效果。
     之前产生AI合并仅仅是为了空位得分。修改时间,5.18, 21:02"""

    @staticmethod
    def rival_chessman_score(value: int):  # 返回对方每个值对应多少得分,封装在函数中便于修改，在移动模式的代价函数中调用
        return -value * int(pow(2, value - 1))
        # 这里的返回分数修改为与my_chessman_score 一致了 5.24日
        # 权重下调 5.25日

    @staticmethod
    def be_occupied_score(value: int):
        """在己方棋盘被对方占据的情况返回的分数,返回的是一个负分，鼓励AI吃掉对方在自己位置的棋子
        封装在函数中便于修改，在移动模式的代价函数中调用"""
        return -int(pow(2, value))  # 权重下调 5.25日

    @staticmethod
    def occupy_score(value: int):
        """在对方棋盘被己方占据的情况返回的分数，返回一个正分，不再鼓励AI将棋子移回本方 5.25日"""
        return 2

    @staticmethod
    def threaten_score(value: int):
        """对应的是棋子存在吃对方和被对方吃的可能性时返回的分数,
        封在函数中便于修改，在get_neighbor_1函数中调用"""
        return int(pow(2, value))

    @staticmethod
    def put_chessman_score(value_1, value_2, value_3, value_4):
        score = 0
        if value_1 and value_2:
            if (value_1[1] != value_2[1]) and value_1[0] == value_2[0]:
                return float("inf")
            elif value_1[1] == value_2[1] and value_1[0] >= 4 and value_2[0] >= 4:
                score += pow(2, value_1[0]) + pow(2, value_2[0])
        if value_3 and value_4:
            if value_3[1] != value_4[1] and value_3[0] == value_4[0]:
                return float("inf")
            elif value_3[1] == value_4[1] and value_3[0] >= 4 and value_4[0] >= 4:
                score += pow(2, value_3[0]) + pow(2, value_4[0])
        return score

    """对put_chessman_score进行了重写,5.25日"""

    @staticmethod
    def update_position(position, direction):  # 在目前位置向给定方向移动一格
        if direction == 0:  # 对应向上移动
            return position[0] - 1, position[1]
        elif direction == 1:  # 对应向下移动
            return position[0] + 1, position[1]
        elif direction == 2:  # 对应向左移动
            return position[0], position[1] - 1
        elif direction == 3:  # 对应向右移动
            return position[0], position[1] + 1
    # update_function 进行了修改,之前坐标加减搞错了，导致AI在决策上出了一些问题 修改时间:5.18,20:35
